package 力扣.动态规划.线性DP;

public class 打家劫舍II_213 {
    //这里是一个环，但是你不知道偷没偷第一家。
    //所以走两边dp:第一遍：从偷第一家开始，第二遍：偷第二家开始
    public int rob(int[] nums) {
       if (nums == null || nums.length == 0){
           return 0;
       }
        final int N = nums.length;
       if (N == 1){//只有一个元素
           return nums[0];
       }

        int ans1 = stealSub(nums, 0, N - 1);//从第一家到倒数第二家
        int ans2 = stealSub(nums, 1, N);//从第二家到倒数第一家
        return Math.max(ans1, ans2);
    }
    private int stealSub(int[] nums,int m,int n){
        if (m >= n){
            return 0;
        }
        int[] dp = new int[n];
        if (n - m == 1){//说明只有一个元素
            return nums[m];
        }
        dp[m] = nums[m];
        dp[m + 1] = Math.max(nums[m],nums[m + 1]);//给前两个数初始化
        for (int i = m + 2; i < n; i++) {
            dp[i] = Math.max(dp[i - 2]+nums[i],dp[i - 1]);
        }
        return dp[n - 1];
    }

}
